/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-08-01
 * Time: 18:51
 */
class Solution27 {
    public int maxSumDivThree(int[] nums) {
        //1.正难则反
        int INF = 0x3f3f3f3f;
        int sum = 0,x1 = INF,x2 = INF,y1= INF,y2 = INF;
        for(int x : nums) {
            sum += x;
            if(x % 3 == 1) {
                if(x < x1) {
                    x2 = x1;
                    x1 = x;
                }else if(x < x2){
                    x2 = x;
                }
            }else if(x % 3 == 2) {
                if(x < y1) {
                    y2 = y1;
                    y1 = x;
                }else if(x < y2){
                    y2 = x;
                }
            }
        }

        //分类讨论
        if(sum % 3 == 0) {
            return sum;
        }else if(sum % 3 == 1) {
            return Math.max(sum-x1,sum-y1-y2);
        }else {
            return Math.max(sum-y1,sum-x1-x2);
        }
    }
}

//动态规划解法
//class Solution {
//    public int maxSumDivThree(int[] nums) {
//
//        int n = nums.length;
//
//        // 1.dp[i][0/1/2]表示前i个数余数为0/1/2的和的最大值
//        int[][] dp = new int[n+1][3];
//        // 2.初始化
//        dp[0][0] = 0; dp[0][1] = Integer.MIN_VALUE; dp[0][2] = Integer.MIN_VALUE;
//
//        // 3.状态转移
//        for(int i = 1; i <= n; i++) {
//            if(nums[i-1] % 3 == 0) {
//                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][0]+nums[i-1]);
//                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][1]+nums[i-1]);
//                dp[i][2] = Math.max(dp[i-1][2],dp[i-1][2]+nums[i-1]);
//            }else if(nums[i-1] % 3 == 1) {
//                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]+nums[i-1]);
//                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+nums[i-1]);
//                dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+nums[i-1]);
//            }else {
//                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+nums[i-1]);
//                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][2]+nums[i-1]);
//                dp[i][2] = Math.max(dp[i-1][2],dp[i-1][0]+nums[i-1]);
//            }
//        }
//        return dp[n][0];
//    }
//}
